package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 1305. 两棵二叉搜索树中的所有元素
 * 2022-05-01 每日一题
 *
 * @author fy
 * @date 2022-05-01 23:28
 */
public class Solution1305 {

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = inOrder(root1);
        List<Integer> list2 = inOrder(root2);
        List<Integer> list = new ArrayList<>();
        int p = 0;
        int q = 0;
        while (p < list1.size() || q < list2.size()) {
            if (p >= list1.size()) {
                list.add(list2.get(q));
                q++;
            } else if (q >= list2.size()) {
                list.add(list1.get(p));
                p++;
            } else if (list1.get(p) <= list2.get(q)) {
                list.add(list1.get(p));
                p++;
            } else if (list1.get(p) > list2.get(q)) {
                list.add(list2.get(q));
                q++;
            }
        }
        return list;
    }

    private List<Integer> inOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }

}
